package sortAlgorithm;

/**
 * 归并排序
 * 
 * @author YNS
 *
 */
public class MergeSort {
	public static int[] sort(int[] source) {
		return merge(source, 0, source.length - 1);
	}

	private static int[] merge(int[] source, int low, int high) {
		int center = (high + low) / 2;

		if (low < high) {
			merge(source, low, center);
			merge(source, center + 1, high);
			mergeSort(source, low, center, high);
		}

		return source;
	}

	private static void mergeSort(int[] source, int low, int center, int high) {
		int[] tempArr = new int[source.length];
		int i = low;
		int j = center + 1;

		int index = 0;

		while (i <= center && j <= high) {

			if (source[i] < source[j]) {
				tempArr[index] = source[i];
				i++;
			} else {
				tempArr[index] = source[j];
				j++;
			}
			index++;
		}

		while (i <= center) {
			tempArr[index] = source[i];
			i++;
			index++;
		}

		while (j <= high) {
			tempArr[index] = source[j];
			j++;
			index++;
		}

		for (int k = 0; k < index; k++) {
			source[k + low] = tempArr[k];
		}
	}
}
